<!DOCTYPE html><html><head>
      <title>&#x692D;&#x5706;&#x66F2;&#x7EBF;&#x52A0;&#x5BC6;&#x6570;&#x5B66;&#x57FA;&#x7840;</title>
      <meta charset="utf-8">
      <meta name="viewport" content="width=device-width, initial-scale=1.0">
      
      
        <script type="text/x-mathjax-config">
          MathJax.Hub.Config({"extensions":["tex2jax.js"],"jax":["input/TeX","output/HTML-CSS"],"messageStyle":"none","tex2jax":{"processEnvironments":false,"processEscapes":true,"inlineMath":[["$","$"],["\\(","\\)"]],"displayMath":[["$$","$$"],["\\[","\\]"]]},"TeX":{"extensions":["AMSmath.js","AMSsymbols.js","noErrors.js","noUndefined.js"]},"HTML-CSS":{"availableFonts":["TeX"]}});
        </script>
        <script type="text/javascript" async src="https://cdnjs.cloudflare.com/ajax/libs/mathjax/2.7.5/MathJax.js"></script>
        
      
      
      
      
      
      
      
      
      
      <style>
      /**
 * prism.js Github theme based on GitHub's theme.
 * @author Sam Clarke
 */
code[class*="language-"],
pre[class*="language-"] {
  color: #333;
  background: none;
  font-family: Consolas, "Liberation Mono", Menlo, Courier, monospace;
  text-align: left;
  white-space: pre;
  word-spacing: normal;
  word-break: normal;
  word-wrap: normal;
  line-height: 1.4;

  -moz-tab-size: 8;
  -o-tab-size: 8;
  tab-size: 8;

  -webkit-hyphens: none;
  -moz-hyphens: none;
  -ms-hyphens: none;
  hyphens: none;
}

/* Code blocks */
pre[class*="language-"] {
  padding: .8em;
  overflow: auto;
  /* border: 1px solid #ddd; */
  border-radius: 3px;
  /* background: #fff; */
  background: #f5f5f5;
}

/* Inline code */
:not(pre) > code[class*="language-"] {
  padding: .1em;
  border-radius: .3em;
  white-space: normal;
  background: #f5f5f5;
}

.token.comment,
.token.blockquote {
  color: #969896;
}

.token.cdata {
  color: #183691;
}

.token.doctype,
.token.punctuation,
.token.variable,
.token.macro.property {
  color: #333;
}

.token.operator,
.token.important,
.token.keyword,
.token.rule,
.token.builtin {
  color: #a71d5d;
}

.token.string,
.token.url,
.token.regex,
.token.attr-value {
  color: #183691;
}

.token.property,
.token.number,
.token.boolean,
.token.entity,
.token.atrule,
.token.constant,
.token.symbol,
.token.command,
.token.code {
  color: #0086b3;
}

.token.tag,
.token.selector,
.token.prolog {
  color: #63a35c;
}

.token.function,
.token.namespace,
.token.pseudo-element,
.token.class,
.token.class-name,
.token.pseudo-class,
.token.id,
.token.url-reference .token.variable,
.token.attr-name {
  color: #795da3;
}

.token.entity {
  cursor: help;
}

.token.title,
.token.title .token.punctuation {
  font-weight: bold;
  color: #1d3e81;
}

.token.list {
  color: #ed6a43;
}

.token.inserted {
  background-color: #eaffea;
  color: #55a532;
}

.token.deleted {
  background-color: #ffecec;
  color: #bd2c00;
}

.token.bold {
  font-weight: bold;
}

.token.italic {
  font-style: italic;
}


/* JSON */
.language-json .token.property {
  color: #183691;
}

.language-markup .token.tag .token.punctuation {
  color: #333;
}

/* CSS */
code.language-css,
.language-css .token.function {
  color: #0086b3;
}

/* YAML */
.language-yaml .token.atrule {
  color: #63a35c;
}

code.language-yaml {
  color: #183691;
}

/* Ruby */
.language-ruby .token.function {
  color: #333;
}

/* Markdown */
.language-markdown .token.url {
  color: #795da3;
}

/* Makefile */
.language-makefile .token.symbol {
  color: #795da3;
}

.language-makefile .token.variable {
  color: #183691;
}

.language-makefile .token.builtin {
  color: #0086b3;
}

/* Bash */
.language-bash .token.keyword {
  color: #0086b3;
}

/* highlight */
pre[data-line] {
  position: relative;
  padding: 1em 0 1em 3em;
}
pre[data-line] .line-highlight-wrapper {
  position: absolute;
  top: 0;
  left: 0;
  background-color: transparent;
  display: block;
  width: 100%;
}

pre[data-line] .line-highlight {
  position: absolute;
  left: 0;
  right: 0;
  padding: inherit 0;
  margin-top: 1em;
  background: hsla(24, 20%, 50%,.08);
  background: linear-gradient(to right, hsla(24, 20%, 50%,.1) 70%, hsla(24, 20%, 50%,0));
  pointer-events: none;
  line-height: inherit;
  white-space: pre;
}

pre[data-line] .line-highlight:before, 
pre[data-line] .line-highlight[data-end]:after {
  content: attr(data-start);
  position: absolute;
  top: .4em;
  left: .6em;
  min-width: 1em;
  padding: 0 .5em;
  background-color: hsla(24, 20%, 50%,.4);
  color: hsl(24, 20%, 95%);
  font: bold 65%/1.5 sans-serif;
  text-align: center;
  vertical-align: .3em;
  border-radius: 999px;
  text-shadow: none;
  box-shadow: 0 1px white;
}

pre[data-line] .line-highlight[data-end]:after {
  content: attr(data-end);
  top: auto;
  bottom: .4em;
}html body{font-family:"Helvetica Neue",Helvetica,"Segoe UI",Arial,freesans,sans-serif;font-size:16px;line-height:1.6;color:#333;background-color:#fff;overflow:initial;box-sizing:border-box;word-wrap:break-word}html body>:first-child{margin-top:0}html body h1,html body h2,html body h3,html body h4,html body h5,html body h6{line-height:1.2;margin-top:1em;margin-bottom:16px;color:#000}html body h1{font-size:2.25em;font-weight:300;padding-bottom:.3em}html body h2{font-size:1.75em;font-weight:400;padding-bottom:.3em}html body h3{font-size:1.5em;font-weight:500}html body h4{font-size:1.25em;font-weight:600}html body h5{font-size:1.1em;font-weight:600}html body h6{font-size:1em;font-weight:600}html body h1,html body h2,html body h3,html body h4,html body h5{font-weight:600}html body h5{font-size:1em}html body h6{color:#5c5c5c}html body strong{color:#000}html body del{color:#5c5c5c}html body a:not([href]){color:inherit;text-decoration:none}html body a{color:#08c;text-decoration:none}html body a:hover{color:#00a3f5;text-decoration:none}html body img{max-width:100%}html body>p{margin-top:0;margin-bottom:16px;word-wrap:break-word}html body>ul,html body>ol{margin-bottom:16px}html body ul,html body ol{padding-left:2em}html body ul.no-list,html body ol.no-list{padding:0;list-style-type:none}html body ul ul,html body ul ol,html body ol ol,html body ol ul{margin-top:0;margin-bottom:0}html body li{margin-bottom:0}html body li.task-list-item{list-style:none}html body li>p{margin-top:0;margin-bottom:0}html body .task-list-item-checkbox{margin:0 .2em .25em -1.8em;vertical-align:middle}html body .task-list-item-checkbox:hover{cursor:pointer}html body blockquote{margin:16px 0;font-size:inherit;padding:0 15px;color:#5c5c5c;background-color:#f0f0f0;border-left:4px solid #d6d6d6}html body blockquote>:first-child{margin-top:0}html body blockquote>:last-child{margin-bottom:0}html body hr{height:4px;margin:32px 0;background-color:#d6d6d6;border:0 none}html body table{margin:10px 0 15px 0;border-collapse:collapse;border-spacing:0;display:block;width:100%;overflow:auto;word-break:normal;word-break:keep-all}html body table th{font-weight:bold;color:#000}html body table td,html body table th{border:1px solid #d6d6d6;padding:6px 13px}html body dl{padding:0}html body dl dt{padding:0;margin-top:16px;font-size:1em;font-style:italic;font-weight:bold}html body dl dd{padding:0 16px;margin-bottom:16px}html body code{font-family:Menlo,Monaco,Consolas,'Courier New',monospace;font-size:.85em !important;color:#000;background-color:#f0f0f0;border-radius:3px;padding:.2em 0}html body code::before,html body code::after{letter-spacing:-0.2em;content:"\00a0"}html body pre>code{padding:0;margin:0;font-size:.85em !important;word-break:normal;white-space:pre;background:transparent;border:0}html body .highlight{margin-bottom:16px}html body .highlight pre,html body pre{padding:1em;overflow:auto;font-size:.85em !important;line-height:1.45;border:#d6d6d6;border-radius:3px}html body .highlight pre{margin-bottom:0;word-break:normal}html body pre code,html body pre tt{display:inline;max-width:initial;padding:0;margin:0;overflow:initial;line-height:inherit;word-wrap:normal;background-color:transparent;border:0}html body pre code:before,html body pre tt:before,html body pre code:after,html body pre tt:after{content:normal}html body p,html body blockquote,html body ul,html body ol,html body dl,html body pre{margin-top:0;margin-bottom:16px}html body kbd{color:#000;border:1px solid #d6d6d6;border-bottom:2px solid #c7c7c7;padding:2px 4px;background-color:#f0f0f0;border-radius:3px}@media print{html body{background-color:#fff}html body h1,html body h2,html body h3,html body h4,html body h5,html body h6{color:#000;page-break-after:avoid}html body blockquote{color:#5c5c5c}html body pre{page-break-inside:avoid}html body table{display:table}html body img{display:block;max-width:100%;max-height:100%}html body pre,html body code{word-wrap:break-word;white-space:pre}}.markdown-preview{width:100%;height:100%;box-sizing:border-box}.markdown-preview .pagebreak,.markdown-preview .newpage{page-break-before:always}.markdown-preview pre.line-numbers{position:relative;padding-left:3.8em;counter-reset:linenumber}.markdown-preview pre.line-numbers>code{position:relative}.markdown-preview pre.line-numbers .line-numbers-rows{position:absolute;pointer-events:none;top:1em;font-size:100%;left:0;width:3em;letter-spacing:-1px;border-right:1px solid #999;-webkit-user-select:none;-moz-user-select:none;-ms-user-select:none;user-select:none}.markdown-preview pre.line-numbers .line-numbers-rows>span{pointer-events:none;display:block;counter-increment:linenumber}.markdown-preview pre.line-numbers .line-numbers-rows>span:before{content:counter(linenumber);color:#999;display:block;padding-right:.8em;text-align:right}.markdown-preview .mathjax-exps .MathJax_Display{text-align:center !important}.markdown-preview:not([for="preview"]) .code-chunk .btn-group{display:none}.markdown-preview:not([for="preview"]) .code-chunk .status{display:none}.markdown-preview:not([for="preview"]) .code-chunk .output-div{margin-bottom:16px}.scrollbar-style::-webkit-scrollbar{width:8px}.scrollbar-style::-webkit-scrollbar-track{border-radius:10px;background-color:transparent}.scrollbar-style::-webkit-scrollbar-thumb{border-radius:5px;background-color:rgba(150,150,150,0.66);border:4px solid rgba(150,150,150,0.66);background-clip:content-box}html body[for="html-export"]:not([data-presentation-mode]){position:relative;width:100%;height:100%;top:0;left:0;margin:0;padding:0;overflow:auto}html body[for="html-export"]:not([data-presentation-mode]) .markdown-preview{position:relative;top:0}@media screen and (min-width:914px){html body[for="html-export"]:not([data-presentation-mode]) .markdown-preview{padding:2em calc(50% - 457px + 2em)}}@media screen and (max-width:914px){html body[for="html-export"]:not([data-presentation-mode]) .markdown-preview{padding:2em}}@media screen and (max-width:450px){html body[for="html-export"]:not([data-presentation-mode]) .markdown-preview{font-size:14px !important;padding:1em}}@media print{html body[for="html-export"]:not([data-presentation-mode]) #sidebar-toc-btn{display:none}}html body[for="html-export"]:not([data-presentation-mode]) #sidebar-toc-btn{position:fixed;bottom:8px;left:8px;font-size:28px;cursor:pointer;color:inherit;z-index:99;width:32px;text-align:center;opacity:.4}html body[for="html-export"]:not([data-presentation-mode])[html-show-sidebar-toc] #sidebar-toc-btn{opacity:1}html body[for="html-export"]:not([data-presentation-mode])[html-show-sidebar-toc] .md-sidebar-toc{position:fixed;top:0;left:0;width:300px;height:100%;padding:32px 0 48px 0;font-size:14px;box-shadow:0 0 4px rgba(150,150,150,0.33);box-sizing:border-box;overflow:auto;background-color:inherit}html body[for="html-export"]:not([data-presentation-mode])[html-show-sidebar-toc] .md-sidebar-toc::-webkit-scrollbar{width:8px}html body[for="html-export"]:not([data-presentation-mode])[html-show-sidebar-toc] .md-sidebar-toc::-webkit-scrollbar-track{border-radius:10px;background-color:transparent}html body[for="html-export"]:not([data-presentation-mode])[html-show-sidebar-toc] .md-sidebar-toc::-webkit-scrollbar-thumb{border-radius:5px;background-color:rgba(150,150,150,0.66);border:4px solid rgba(150,150,150,0.66);background-clip:content-box}html body[for="html-export"]:not([data-presentation-mode])[html-show-sidebar-toc] .md-sidebar-toc a{text-decoration:none}html body[for="html-export"]:not([data-presentation-mode])[html-show-sidebar-toc] .md-sidebar-toc ul{padding:0 1.6em;margin-top:.8em}html body[for="html-export"]:not([data-presentation-mode])[html-show-sidebar-toc] .md-sidebar-toc li{margin-bottom:.8em}html body[for="html-export"]:not([data-presentation-mode])[html-show-sidebar-toc] .md-sidebar-toc ul{list-style-type:none}html body[for="html-export"]:not([data-presentation-mode])[html-show-sidebar-toc] .markdown-preview{left:300px;width:calc(100% -  300px);padding:2em calc(50% - 457px -  150px);margin:0;box-sizing:border-box}@media screen and (max-width:1274px){html body[for="html-export"]:not([data-presentation-mode])[html-show-sidebar-toc] .markdown-preview{padding:2em}}@media screen and (max-width:450px){html body[for="html-export"]:not([data-presentation-mode])[html-show-sidebar-toc] .markdown-preview{width:100%}}html body[for="html-export"]:not([data-presentation-mode]):not([html-show-sidebar-toc]) .markdown-preview{left:50%;transform:translateX(-50%)}html body[for="html-export"]:not([data-presentation-mode]):not([html-show-sidebar-toc]) .md-sidebar-toc{display:none}
/* Please visit the URL below for more information: */
/*   https://shd101wyy.github.io/markdown-preview-enhanced/#/customize-css */

      </style>
    </head>
    <body for="html-export">
      <div class="mume markdown-preview  ">
      <h1 class="mume-header" id="%E6%A4%AD%E5%9C%86%E5%8A%A0%E5%AF%86%E6%95%B0%E5%AD%A6%E5%9F%BA%E7%A1%80">&#x692D;&#x5706;&#x52A0;&#x5BC6;&#x6570;&#x5B66;&#x57FA;&#x7840;</h1>

<p><span id="toc"></span></p>
<ul>
<li><a href="#%E6%A4%AD%E5%9C%86%E5%8A%A0%E5%AF%86%E6%95%B0%E5%AD%A6%E5%9F%BA%E7%A1%80">&#x692D;&#x5706;&#x52A0;&#x5BC6;&#x6570;&#x5B66;&#x57FA;&#x7840;</a>
<ul>
<li><a href="#%E6%9C%89%E9%99%90%E7%BE%A4toc">&#x6709;&#x9650;&#x7FA4;</a></li>
<li><a href="#%E5%9F%9Ff_qtoc">&#x57DF;<span class="mathjax-exps">$F_q$</span></a>
<ul>
<li><a href="#%E5%9F%9Ff_ptoc">&#x57DF;<span class="mathjax-exps">$F_p$</span></a></li>
<li><a href="#%E5%9F%9Ff_2mtoc">&#x57DF;<span class="mathjax-exps">$F_{2^m}$</span></a>
<ul>
<li><a href="#f_2m%E7%9A%84%E5%A4%9A%E9%A1%B9%E5%BC%8F%E5%9F%BA%E8%A1%A8%E7%A4%BAtoc"><span class="mathjax-exps">$F_{2^m}$</span>&#x7684;&#x591A;&#x9879;&#x5F0F;&#x57FA;&#x8868;&#x793A;</a></li>
<li><a href="#f_2m%E7%9A%84%E9%AB%98%E6%96%AF%E8%A7%84%E8%8C%83%E5%9F%BA%E8%A1%A8%E7%A4%BAtoc"><span class="mathjax-exps">$F_{2^m}$</span>&#x7684;&#x9AD8;&#x65AF;&#x89C4;&#x8303;&#x57FA;&#x8868;&#x793A;</a></li>
</ul>
</li>
</ul>
</li>
<li><a href="#%E6%A4%AD%E5%9C%86%E6%9B%B2%E7%BA%BFtoc">&#x692D;&#x5706;&#x66F2;&#x7EBF;</a>
<ul>
<li><a href="#%E5%AE%9A%E4%B9%89%E5%9C%A8%E5%9F%9Ff_p%E7%9A%84%E6%A4%AD%E5%9C%86%E6%9B%B2%E7%BA%BFtoc">&#x5B9A;&#x4E49;&#x5728;&#x57DF;<span class="mathjax-exps">$F_p$</span>&#x7684;&#x692D;&#x5706;&#x66F2;&#x7EBF;</a></li>
<li><a href="#%E5%AE%9A%E4%B9%89%E5%9C%A8%E5%9F%9Ff_2m%E4%B8%8A%E7%9A%84%E6%A4%AD%E5%9C%86%E6%9B%B2%E7%BA%BFtoc">&#x5B9A;&#x4E49;&#x5728;&#x57DF;<span class="mathjax-exps">$F_{2^m}$</span>&#x4E0A;&#x7684;&#x692D;&#x5706;&#x66F2;&#x7EBF;</a></li>
</ul>
</li>
<li><a href="#%E6%9C%89%E9%99%90%E5%9F%9F%E5%92%8C%E6%A8%A1%E8%BF%90%E7%AE%97toc">&#x6709;&#x9650;&#x57DF;&#x548C;&#x6A21;&#x8FD0;&#x7B97;</a>
<ul>
<li><a href="#%E6%9C%89%E9%99%90%E5%9F%9F%E4%B8%8A%E7%9A%84%E5%B9%82%E8%BF%90%E7%AE%97toc">&#x6709;&#x9650;&#x57DF;&#x4E0A;&#x7684;&#x5E42;&#x8FD0;&#x7B97;</a></li>
<li><a href="#%E6%9C%89%E9%99%90%E5%9F%9F%E4%B8%8A%E7%9A%84%E9%80%86%E8%BF%90%E7%AE%97toc">&#x6709;&#x9650;&#x57DF;&#x4E0A;&#x7684;&#x9006;&#x8FD0;&#x7B97;</a></li>
<li><a href="#lucas%E5%BA%8F%E5%88%97%E7%9A%84%E7%94%9F%E6%88%90toc">Lucas&#x5E8F;&#x5217;&#x7684;&#x751F;&#x6210;</a></li>
<li><a href="#%E7%B4%A0%E6%95%B0%E6%A8%A1%E7%9A%84%E5%B9%B3%E6%96%B9%E6%A0%B9toc">&#x7D20;&#x6570;&#x6A21;&#x7684;&#x5E73;&#x65B9;&#x6839;</a></li>
<li><a href="#%E8%BF%B9%E5%92%8C%E5%8D%8A%E8%BF%B9%E5%87%BD%E6%95%B0toc">&#x8FF9;&#x548C;&#x534A;&#x8FF9;&#x51FD;&#x6570;</a></li>
<li><a href="#f_2m%E4%B8%8A%E7%9A%84%E4%BA%8C%E6%AC%A1%E7%AD%89%E5%BC%8F%E6%B1%82%E8%A7%A3toc"><span class="mathjax-exps">$F_{2^m}$</span>&#x4E0A;&#x7684;&#x4E8C;&#x6B21;&#x7B49;&#x5F0F;&#x6C42;&#x89E3;</a></li>
<li><a href="#%E9%AA%8C%E8%AF%81%E7%94%9F%E6%88%90%E5%AD%90%E7%9A%84%E9%98%B6%E7%9A%84%E5%90%88%E6%B3%95%E6%80%A7toc">&#x9A8C;&#x8BC1;&#x751F;&#x6210;&#x5B50;&#x7684;&#x9636;&#x7684;&#x5408;&#x6CD5;&#x6027;</a></li>
<li><a href="#%E7%94%9F%E6%88%90%E5%AD%90%E9%98%B6%E7%9A%84%E8%AE%A1%E7%AE%97toc">&#x751F;&#x6210;&#x5B50;&#x9636;&#x7684;&#x8BA1;&#x7B97;</a></li>
<li><a href="#%E6%B1%82%E6%8C%87%E5%AE%9A%E9%98%B6%E6%95%B0%E7%9A%84%E7%94%9F%E6%88%90%E5%AD%90toc">&#x6C42;&#x6307;&#x5B9A;&#x9636;&#x6570;&#x7684;&#x751F;&#x6210;&#x5B50;</a></li>
</ul>
</li>
<li><a href="#%E6%9C%89%E9%99%90%E5%9F%9F%E4%B8%8A%E7%9A%84%E5%A4%9A%E9%A1%B9%E5%BC%8Ftoc">&#x6709;&#x9650;&#x57DF;&#x4E0A;&#x7684;&#x591A;&#x9879;&#x5F0F;</a>
<ul>
<li><a href="#%E6%9C%89%E9%99%90%E5%9F%9F%E4%B8%8A%E7%9A%84%E5%A4%9A%E9%A1%B9%E5%BC%8Fgcd%E6%B1%82%E8%A7%A3toc">&#x6709;&#x9650;&#x57DF;&#x4E0A;&#x7684;&#x591A;&#x9879;&#x5F0F;GCD&#x6C42;&#x89E3;</a></li>
<li><a href="#%E8%AE%A1%E7%AE%97f_2m%E4%B8%8A%E7%9A%84%E4%B8%8D%E5%8F%AF%E7%BA%A6%E5%A4%9A%E9%A1%B9%E5%BC%8F%E7%9A%84%E6%A0%B9toc">&#x8BA1;&#x7B97;<span class="mathjax-exps">$F_{2^m}$</span>&#x4E0A;&#x7684;&#x4E0D;&#x53EF;&#x7EA6;&#x591A;&#x9879;&#x5F0F;&#x7684;&#x6839;</a></li>
</ul>
</li>
<li><a href="#%E6%95%B0%E8%AE%BA%E7%9B%B8%E5%85%B3toc">&#x6570;&#x8BBA;&#x76F8;&#x5173;</a>
<ul>
<li><a href="#jacobi%E7%AC%A6%E5%8F%B7%E7%9A%84%E8%AE%A1%E7%AE%97toc">Jacobi&#x7B26;&#x53F7;&#x7684;&#x8BA1;&#x7B97;</a></li>
<li><a href="#%E6%B1%82%E6%AD%A3%E6%95%B4%E6%95%B0%E6%A8%A12%E7%9A%84%E6%AC%A1%E5%B9%82%E7%9A%84%E5%B9%B3%E6%96%B9%E6%A0%B9toc">&#x6C42;&#x6B63;&#x6574;&#x6570;&#x6A21;2&#x7684;&#x6B21;&#x5E42;&#x7684;&#x5E73;&#x65B9;&#x6839;</a></li>
<li><a href="#%E5%A4%9A%E9%A1%B9%E5%BC%8F%E7%9A%84%E5%B9%82%E6%A8%A1toc">&#x591A;&#x9879;&#x5F0F;&#x7684;&#x5E42;&#x6A21;</a></li>
</ul>
</li>
<li><a href="#%E5%8F%82%E8%80%83%E8%B5%84%E6%96%99toc">&#x53C2;&#x8003;&#x8D44;&#x6599;</a></li>
</ul>
</li>
</ul>
<h2 class="mume-header" id="%E6%9C%89%E9%99%90%E7%BE%A4toc"><a href="#toc">&#x6709;&#x9650;&#x7FA4;</a></h2>

<ul>
<li>&#x8BB0;&#x6709;&#x4E00;&#x4E2A;&#x96C6;&#x5408;<span class="mathjax-exps">$S$</span>, &#x53CA;&#x5B9A;&#x4E49;&#x5728;<span class="mathjax-exps">$S$</span>&#x4E0A;&#x7684;&#x6EE1;&#x8DB3;&#x5982;&#x4E0B;&#x6027;&#x8D28;&#x7684;&#x4E8C;&#x5143;&#x8FD0;&#x7B97;<span class="mathjax-exps">$\oplus$</span>, &#x5219;<span class="mathjax-exps">$(S,\oplus)$</span>&#x79F0;&#x4E3A;<strong>&#x7FA4;</strong>:
<ul>
<li><strong>&#x5C01;&#x95ED;&#x6027;</strong>: &#x5BF9;<span class="mathjax-exps">$\forall a, b\in S$</span>, &#x6709;<span class="mathjax-exps">$a\oplus b \in S$</span>.</li>
<li><strong>&#x5355;&#x4F4D;&#x5143;</strong>: &#x5B58;&#x5728;&#x4E00;&#x4E2A;&#x552F;&#x4E00;&#x7684;&#x5143;&#x7D20;<span class="mathjax-exps">$e \in S$</span>, &#x6EE1;&#x8DB3;<span class="mathjax-exps">$\forall a \in S, e\oplus a = a\oplus e = a$</span>, <span class="mathjax-exps">$e$</span>&#x79F0;&#x4E3A;&#x8BE5;&#x7FA4;&#x7684;&#x5355;&#x4F4D;&#x5143;;</li>
<li><strong>&#x7ED3;&#x5408;&#x5F8B;</strong>: <span class="mathjax-exps">$\forall a, b, c \in S$</span>, &#x6EE1;&#x8DB3;<span class="mathjax-exps">$(a\oplus b)\oplus c=a\oplus(b\oplus c)$</span>;</li>
<li><strong>&#x9006;&#x5143;</strong>: <span class="mathjax-exps">$\forall a \in S$</span>, &#x5B58;&#x5728;&#x552F;&#x4E00;&#x7684;<span class="mathjax-exps">$b \in S$</span>, &#x6EE1;&#x8DB3;<span class="mathjax-exps">$a\oplus b = b\oplus a = e$</span>;</li>
</ul>
</li>
<li>&#x8BB0;&#x6709;&#x4E00;&#x7FA4;<span class="mathjax-exps">$(S, \oplus)$</span>:
<ul>
<li>&#x82E5;<span class="mathjax-exps">$\forall a, b\in S$</span>, &#x6EE1;&#x8DB3;<span class="mathjax-exps">$a\oplus b = b\oplus a$</span>, &#x5219;&#x8BE5;&#x7FA4;&#x79F0;&#x4E3A;<strong>&#x4EA4;&#x6362;&#x7FA4;</strong>;</li>
<li>&#x82E5;<span class="mathjax-exps">$|S|&lt;\infty$</span>, &#x5219;&#x8BE5;&#x7FA4;&#x79F0;&#x4E3A;<strong>&#x6709;&#x9650;&#x7FA4;</strong>;</li>
</ul>
</li>
<li>&#x8BB0;&#x6709;&#x4E00;&#x4EA4;&#x6362;&#x7FA4;<span class="mathjax-exps">$(S, \oplus)$</span>. &#x82E5;&#x5B58;&#x5728;&#x4E00;&#x79CD;&#x4E8C;&#x5143;&#x8FD0;&#x7B97;<span class="mathjax-exps">$\odot$</span>&#x6EE1;&#x8DB3;&#x4EE5;&#x4E0B;&#x6027;&#x8D28;, &#x5219;&#x79F0;&#x5176;&#x4E3A;<strong>&#x73AF;</strong>:
<ul>
<li><strong>&#x5C01;&#x95ED;&#x6027;</strong>: &#x82E5;<span class="mathjax-exps">$\forall a,b \in S$</span>, &#x6EE1;&#x8DB3;<span class="mathjax-exps">$a \odot c \in S$</span>;</li>
<li><strong>&#x5206;&#x914D;&#x5F8B;</strong>: &#x82E5;<span class="mathjax-exps">$\forall a,b,c \in S$</span>, &#x6EE1;&#x8DB3;<span class="mathjax-exps">$a\odot (b \oplus c) = (a\odot b)\oplus (a\odot c), (a \oplus b)\odot c = (a \odot c)\oplus (b\odot c)$</span>;</li>
</ul>
</li>
<li>&#x8BB0;&#x6709;&#x4E00;&#x4E2A;&#x73AF;<span class="mathjax-exps">$(S, \oplus, \odot)$</span>, &#x82E5;&#x5176;&#x6EE1;&#x8DB3;&#x5982;&#x4E0B;&#x6027;&#x8D28;, &#x5219;&#x79F0;&#x5176;&#x4E3A;<strong>&#x57DF;</strong>:
<ul>
<li>&#x5BF9;&#x4E8E;<span class="mathjax-exps">$\odot$</span>&#x8FD0;&#x7B97;, &#x5B58;&#x5728;&#x552F;&#x4E00;&#x7684;<strong>&#x5355;&#x4F4D;&#x5143;</strong><span class="mathjax-exps">$g$</span>, &#x6EE1;&#x8DB3;<span class="mathjax-exps">$g\in S, g\ne e, \forall a, a\odot g = g\odot a = a$</span>;</li>
<li>&#x5BF9;&#x4E8E;<span class="mathjax-exps">$\odot$</span>&#x8FD0;&#x7B97;&#x5B58;&#x5728;<strong>&#x9006;&#x5143;</strong>, &#x5BF9;&#x4E8E;<span class="mathjax-exps">$\forall a\in S \land a \ne e$</span>, &#x5B58;&#x5728;&#x552F;&#x4E00;&#x7684;<span class="mathjax-exps">$b\in S, a\odot b = b\odot a = g$</span>;</li>
<li>&#x5BF9;&#x4E8E;<span class="mathjax-exps">$\odot$</span>&#x8FD0;&#x7B97;&#x6EE1;&#x8DB3;<strong>&#x4EA4;&#x6362;&#x5F8B;</strong>, &#x5373;<span class="mathjax-exps">$\forall a,b\in S, a\odot b = b\odot a$</span>;</li>
</ul>
</li>
</ul>
<p><a href="https://www.cnblogs.com/mengsuenyan/p/12969712.html">&#x6570;&#x8BBA;&#x76F8;&#x5173;</a>;</p>
<h2 class="mume-header" id="%E5%9F%9Ff_qtoc"><a href="#toc">&#x57DF;<span class="mathjax-exps">$F_q$</span></a></h2>

<p>&#x8BB0;&#x6709;&#x4E00;&#x4E2A;&#x6B63;&#x6574;&#x6570;<span class="mathjax-exps">$q$</span></p>
<h3 class="mume-header" id="%E5%9F%9Ff_ptoc"><a href="#toc">&#x57DF;<span class="mathjax-exps">$F_p$</span></a></h3>

<ul>
<li>&#x82E5;<span class="mathjax-exps">$q \gt e$</span>, &#x5219;&#x6574;&#x6570;&#x96C6;&#x5408;<span class="mathjax-exps">$F_p = \{0,1,2,\dots,q-1\}, p=q$</span>&#x662F;&#x4E00;&#x4E2A;&#x57DF;, &#x8BB0;&#x4E3A;&#x7D20;&#x6570;&#x57DF;<span class="mathjax-exps">$F_p$</span>, &#x5176;&#x4E2D;:
<ul>
<li>&#x5B9A;&#x4E49;<span class="mathjax-exps">$\oplus$</span>&#x8FD0;&#x7B97;&#x4E3A;: <span class="mathjax-exps">$\forall a,b \in F_p, a \oplus b = (a + b) \mod p$</span>;</li>
<li>&#x5B9A;&#x4E49;<span class="mathjax-exps">$\odot$</span>&#x8FD0;&#x7B97;&#x4E3A;: <span class="mathjax-exps">$\forall a,b \in F_p, a\odot b = (a \cdot b) \mod p$</span>;</li>
<li><span class="mathjax-exps">$e = 0$</span>;</li>
<li><span class="mathjax-exps">$g = 1$</span>;</li>
</ul>
</li>
</ul>
<h3 class="mume-header" id="%E5%9F%9Ff_2mtoc"><a href="#toc">&#x57DF;<span class="mathjax-exps">$F_{2^m}$</span></a></h3>

<p>&#x82E5;<span class="mathjax-exps">$q = 2^m$</span>, m&#x662F;&#x7D20;&#x6570;, &#x5219;&#x957F;&#x5EA6;&#x4E3A;<span class="mathjax-exps">$m$</span>&#x7684;&#x4F4D;&#x5B57;&#x7B26;&#x4E32;&#x96C6;&#x5408;<span class="mathjax-exps">$F_{2^m}$</span>&#x662F;&#x4E00;&#x4E2A;&#x57DF;;</p>
<h4 class="mume-header" id="f_2m%E7%9A%84%E5%A4%9A%E9%A1%B9%E5%BC%8F%E5%9F%BA%E8%A1%A8%E7%A4%BAtoc"><a href="#toc"><span class="mathjax-exps">$F_{2^m}$</span>&#x7684;&#x591A;&#x9879;&#x5F0F;&#x57FA;&#x8868;&#x793A;</a></h4>

<p>&#x5728;<span class="mathjax-exps">$F_2$</span>&#x4E0A;&#x7684;&#x57DF;<span class="mathjax-exps">$F_{2^m}$</span>&#x7531;&#x5EA6;&#x4E3A;<span class="mathjax-exps">$m$</span>&#x7684;&#x4E0D;&#x53EF;&#x7EA6;&#x591A;&#x9879;&#x5F0F;<span class="mathjax-exps">$f(x)$</span>&#x5B9A;&#x4E49;, &#x591A;&#x9879;&#x5F0F;&#x96C6;<span class="mathjax-exps">$\{x^{m-1}, x^{m-2},\dots,x,1\}$</span>&#x6784;&#x6210;&#x4E86;&#x5728;<span class="mathjax-exps">$F_2$</span>&#x4E0A;&#x7684;&#x57DF;<span class="mathjax-exps">$F_{2^m}$</span>&#x7684;&#x57FA;, <span class="mathjax-exps">$a\in F_{2^M}, a=(a_{m-1}a_{m-2}\dots a_1 a_0), a(x) = a_{m-1}x^{m-1} + a_{m-2}x^{m-2}+\dots + a_1 x^1 + a_0$</span>;</p>
<ul>
<li><span class="mathjax-exps">$\oplus$</span>&#x5B9A;&#x4E49;&#x4E3A;: <span class="mathjax-exps">$\forall a,b\in F_{2^m}, a\oplus b = a \veebar b$</span>. &#x8FD9;&#x91CC;&#x7684;<span class="mathjax-exps">$\veebar$</span>&#x8868;&#x793A;&#x5F02;&#x6216;, &#x540E;&#x7EED;&#x5728;&#x4E0D;&#x5F71;&#x54CD;&#x7406;&#x89E3;&#x7684;&#x60C5;&#x51B5;&#x4E0B;&#x5F02;&#x6216;&#x4E5F;&#x4F1A;&#x7528;&#x7B26;&#x53F7;<span class="mathjax-exps">$\oplus$</span>&#x8868;&#x793A;;</li>
<li><span class="mathjax-exps">$\odot$</span>&#x5B9A;&#x4E49;&#x4E3A;: <span class="mathjax-exps">$\forall a,b\in F_{2^m}, a\odot b = r, r(x)=(a(x) \cdot b(x)) / f(x)$</span>;</li>
<li><span class="mathjax-exps">$e = 0\dots 00$</span>;</li>
<li><span class="mathjax-exps">$g = 0\dots 01$</span>;</li>
</ul>
<p>&#x5BF9;&#x4E8E;&#x7EA6;&#x5316;&#x591A;&#x9879;&#x5F0F;<span class="mathjax-exps">$f(x)$</span>, &#x5E38;&#x7528;&#x7684;&#x7531;&#x4EE5;&#x4E0B;&#x51E0;&#x79CD;&#x5F62;&#x5F0F;:</p>
<ul>
<li>&#x4E09;&#x9879;&#x5F0F;: <span class="mathjax-exps">$f(x) = x^m + x^k + 1, 1\le k \le m-1$</span>;</li>
<li>&#x4E94;&#x9879;&#x5F0F;: <span class="mathjax-exps">$f(x) = x^m + x^{k_3} + x^{k_2} + x^{k_1} + 1, \quad 1 \le k_1 \le k_2 \le k_3 \le m-1,\quad m \ge 4$</span>;</li>
</ul>
<h4 class="mume-header" id="f_2m%E7%9A%84%E9%AB%98%E6%96%AF%E8%A7%84%E8%8C%83%E5%9F%BA%E8%A1%A8%E7%A4%BAtoc"><a href="#toc"><span class="mathjax-exps">$F_{2^m}$</span>&#x7684;&#x9AD8;&#x65AF;&#x89C4;&#x8303;&#x57FA;&#x8868;&#x793A;</a></h4>

<p><span class="mathjax-exps">$F_2$</span>&#x4E0A;&#x7684;&#x57DF;<span class="mathjax-exps">$F_{2^m}$</span>&#x7684;&#x89C4;&#x8303;&#x57FA;&#x5F62;&#x5F0F;&#x4E3A; <span class="mathjax-exps">$N=\{\alpha,\alpha^2,\alpha^{2^2},\dots,\alpha^{2^{m-1}}\}, a\in F_{2^m}, a=(a_0 a_1\dots a_{m-1})$</span>, &#x5BF9;&#x4E8E;&#x7ED9;&#x5B9A;&#x7684;&#x7D20;&#x6570;<span class="mathjax-exps">$m$</span>&#x548C;&#x5076;&#x6B63;&#x6574;&#x6570;<span class="mathjax-exps">$T$</span>, &#x57DF;<span class="mathjax-exps">$F_{2^m}$</span>&#x6700;&#x591A;&#x6709;&#x4E00;&#x4E2A;&#x7C7B;&#x578B;&#x4E3A;T&#x7684;&#x9AD8;&#x65AF;&#x89C4;&#x8303;&#x57FA;, &#x8BB0;&#x4F5C;<span class="mathjax-exps">$F_{2^m}$</span>&#x7684;Type T&#x578B;&#x9AD8;&#x65AF;&#x89C4;&#x8303;&#x57FA;;</p>
<ul>
<li><span class="mathjax-exps">$\oplus$</span>: <span class="mathjax-exps">$\forall a,b \in F_{2^m}, a\oplus b = a \veebar b$</span>;</li>
<li><span class="mathjax-exps">$e=0\dots 00$</span>;</li>
<li><span class="mathjax-exps">$g = 1\dots 11$</span>;</li>
<li><span class="mathjax-exps">$\odot$</span>:
<ul>
<li><span class="mathjax-exps">$p = T\cdot m + 1$</span>;</li>
<li>&#x751F;&#x6210;&#x4E00;&#x4E2A;&#x9636;&#x4E3A;<span class="mathjax-exps">$T$</span>&#x7684;&#x6574;&#x6570;<span class="mathjax-exps">$u, |&lt;u&gt; \mod p|=T$</span>;</li>
<li>&#x8BA1;&#x7B97;&#x5E8F;&#x5217;<span class="mathjax-exps">$F(1),F(2),\dots,F(p-1)$</span>:
<ul>
<li><span class="mathjax-exps">$w = 1$</span>:</li>
<li><code>for j in 0..=(T-1)</code>:
<ul>
<li><span class="mathjax-exps">$n = w$</span>;</li>
<li><code>for i in 0..=(m-1)</code>:
<ul>
<li><span class="mathjax-exps">$F(n) = i$</span>;</li>
<li><span class="mathjax-exps">$n = 2\cdot n \mod p$</span>;</li>
</ul>
</li>
<li><span class="mathjax-exps">$w = u\cdot w\mod p$</span>;</li>
</ul>
</li>
</ul>
</li>
<li><span class="mathjax-exps">$c_0 = \sum_{k=1}^{p-2}a_{F(k+1)}b_{F(p-k)} = F(a,b)$</span>;</li>
<li><span class="mathjax-exps">$c=(c_0c_1\dots c_{m-1})=a\odot b=(a_0a_1\dots a_{m-1})\cdot (b_0b_1\dots b_{m-1})$</span>:
<ul>
<li><span class="mathjax-exps">$u=(u_0u_1\dots u_{m-1})=(a_0a_1\dots a_{m-1})$</span>;</li>
<li><span class="mathjax-exps">$v=(v_0v_1\dots v_{m-1})=(b_0b_1\dots b_{m-1})$</span>;</li>
<li><code>for k in 0..=(m-1)</code>:
<ul>
<li><span class="mathjax-exps">$c_k=F(u,v)$</span>;</li>
<li><span class="mathjax-exps">$u = u \lll u, v = v \lll v$</span>, <span class="mathjax-exps">$\lll$</span>&#x8868;&#x793A;&#x5FAA;&#x73AF;&#x5DE6;&#x79FB;;</li>
</ul>
</li>
</ul>
</li>
</ul>
</li>
</ul>
<p>&#x5BF9;&#x4E8E;&#x7ED9;&#x5B9A;&#x7684;&#x7D20;&#x6570;<span class="mathjax-exps">$m, T, T\mod 2 = 0$</span>, <span class="mathjax-exps">$F_{2^m}$</span>&#x5B58;&#x5728;<span class="mathjax-exps">$T$</span>&#x578B;&#x9AD8;&#x65AF;&#x89C4;&#x8303;&#x57FA;&#x7684;&#x5B58;&#x5728;&#x53EF;&#x4EE5;&#x901A;&#x8FC7;&#x5982;&#x4E0B;&#x7B97;&#x6CD5;&#x5224;&#x65AD;:</p>
<ul>
<li><span class="mathjax-exps">$p = T\cdot m + 1$</span>;</li>
<li><code>return false</code>, if <span class="mathjax-exps">$p$</span>&#x4E0D;&#x662F;&#x7D20;&#x6570;;</li>
<li>&#x8BA1;&#x7B97;<span class="mathjax-exps">$&lt;2&gt; \mod p$</span>&#x7684;&#x9636;<span class="mathjax-exps">$k$</span>;</li>
<li><span class="mathjax-exps">$h = T\cdot m / k$</span>;</li>
<li><span class="mathjax-exps">$d = gcd(h,m)$</span>;</li>
<li><code>return d=1</code>;</li>
</ul>
<h2 class="mume-header" id="%E6%A4%AD%E5%9C%86%E6%9B%B2%E7%BA%BFtoc"><a href="#toc">&#x692D;&#x5706;&#x66F2;&#x7EBF;</a></h2>

<p>&#x8BB0;&#x6709;&#x692D;&#x5706;&#x66F2;&#x7EBF;<span class="mathjax-exps">$y^2=x^3+ax^2+b$</span>, &#x65E0;&#x7A77;&#x8FDC;&#x70B9;&#x8BB0;&#x4E3A;<span class="mathjax-exps">$\mathcal{O}$</span>, &#x90A3;&#x4E48;&#x53EF;&#x5B9A;&#x4E49;&#x5982;&#x4E0B;&#x8FD0;&#x7B97;:</p>
<ul>
<li>&#x8BB0;<span class="mathjax-exps">$(x_1, y_1), (x_2, y_2)$</span>&#x4E3A;&#x66F2;&#x7EBF;&#x4E0A;&#x7684;&#x4E24;&#x70B9;:
<ul>
<li>&#x5B9A;&#x4E49;<span class="mathjax-exps">$\mathcal{O}+\mathcal{O}=\mathcal{O}$</span>;</li>
<li>&#x82E5;<span class="mathjax-exps">$(x_2, y_2)$</span>&#x4E3A;&#x65E0;&#x7A77;&#x8FDC;&#x70B9;<span class="mathjax-exps">$\mathcal{O}$</span>, &#x5219;&#x5B9A;&#x4E49;<span class="mathjax-exps">$(x_1,y_1)+\mathcal{O}=(x_1,y_1)$</span>;</li>
<li>&#x82E5;<span class="mathjax-exps">$x_1\ne x_2$</span>, &#x90A3;&#x4E48;&#x8FDE;&#x63A5;&#x8FD9;&#x4E24;&#x70B9;&#x7684;&#x76F4;&#x7EBF;&#x4E0E;&#x66F2;&#x7EBF;&#x7684;&#x4EA4;&#x70B9;&#x8BB0;&#x4E3A;<span class="mathjax-exps">$(x_3,y_3)$</span>, &#x5219;&#x5B9A;&#x4E49;&#x52A0;&#x6CD5;&#x8FD0;&#x7B97;&#x6709;: <span class="mathjax-exps">$(x_1,y_1)+(x_2,y_2)=(x_3,-y_3)$</span>;</li>
<li>&#x82E5;<span class="mathjax-exps">$x_1=x_2, y_1\ne -y_2$</span>, &#x90A3;&#x4E48;&#x5B9A;&#x4E49;&#x9006;&#x5143;<span class="mathjax-exps">$(x_1,y_1)+(x_1,-y_1)=\mathcal{O}$</span>;</li>
<li>&#x82E5;<span class="mathjax-exps">$(x_1, y_1), (x_2,y2)$</span>&#x4E3A;&#x66F2;&#x7EBF;&#x4E0A;&#x7684;&#x540C;&#x4E00;&#x70B9;, &#x90A3;&#x4E48;&#x66F2;&#x7EBF;&#x5728;&#x8BE5;&#x70B9;&#x7684;&#x5207;&#x7EBF;&#x4E0E;&#x66F2;&#x7EBF;&#x7684;&#x4EA4;&#x70B9;&#x8BB0;&#x4E3A;<span class="mathjax-exps">$(x_3,y_3)$</span>, &#x5219;&#x5B9A;&#x4E49;&#x4E8C;&#x500D;&#x8FD0;&#x7B97;&#x6709;: <span class="mathjax-exps">$2(x_1,y_1)=(x_3,-y_3)$</span>;</li>
</ul>
</li>
</ul>
<p><strong>&#x6CE8;: &#x4E0B;&#x6587;&#x4E2D;&#x57DF;&#x5143;&#x7D20;&#x7684;<span class="mathjax-exps">$+, \cdot$</span>, &#x5BF9;&#x5E94;&#x7684;&#x662F;&#x4E0A;&#x6587;&#x4E2D;&#x76F8;&#x5E94;&#x57DF;&#x4E2D;&#x5B9A;&#x4E49;&#x7684;<span class="mathjax-exps">$\oplus, \odot$</span></strong>;</p>
<h3 class="mume-header" id="%E5%AE%9A%E4%B9%89%E5%9C%A8%E5%9F%9Ff_p%E7%9A%84%E6%A4%AD%E5%9C%86%E6%9B%B2%E7%BA%BFtoc"><a href="#toc">&#x5B9A;&#x4E49;&#x5728;&#x57DF;<span class="mathjax-exps">$F_p$</span>&#x7684;&#x692D;&#x5706;&#x66F2;&#x7EBF;</a></h3>

<p>&#x8BB0;&#x6709;&#x692D;&#x5706;&#x66F2;&#x7EBF;<span class="mathjax-exps">$y^2=x^3+ax^2+b$</span>, &#x90A3;&#x4E48;&#x7531;&#x7B49;&#x5F0F;<span class="mathjax-exps">$y^2=x^3+ax^2+b\mod p, \{\forall a,b\in F_p, 4a^3+27b^2\not\equiv 0\mod p\}$</span>&#x6240;&#x6709;&#x89E3;<span class="mathjax-exps">$(x,y), x,y\in F_p$</span>&#x53CA;<span class="mathjax-exps">$\mathcal{O}$</span>&#x7EC4;&#x6210;&#x7684;&#x96C6;&#x5408;&#x8BB0;&#x4E3A;<span class="mathjax-exps">$E(F_p)$</span>, &#x90A3;&#x4E48;<span class="mathjax-exps">$E(F_p)$</span>&#x5728;&#x5982;&#x4E0B;&#x4E8C;&#x5143;&#x8FD0;&#x7B97;&#x5B9A;&#x4E49;&#x4E0B;&#x6EE1;&#x8DB3;&#x662F;&#x4E00;&#x4E2A;&#x6709;&#x9650;&#x4EA4;&#x6362;&#x7FA4;:</p>
<ul>
<li><span class="mathjax-exps">$\mathcal{O} + \mathcal{O} = \mathcal{O}$</span>, <span class="mathjax-exps">$\mathcal{O}$</span>&#x5373;&#x4E3A;&#x8BE5;&#x7FA4;&#x7684;&#x5355;&#x4F4D;&#x5143;;</li>
<li><span class="mathjax-exps">$(x,y)+\mathcal{O}=\mathcal{O}+(x,y), \forall (x,y) \in E(F_p)$</span>;</li>
<li><span class="mathjax-exps">$(x,y)+(x,-y)=\mathcal{O}, \forall (x,y) \in E(F_p)$</span>, &#x7FA4;&#x4E2D;&#x5143;&#x7D20;<span class="mathjax-exps">$(x,y)$</span>&#x7684;&#x9006;<span class="mathjax-exps">$-(x,y)$</span>&#x5373;&#x4E3A;<span class="mathjax-exps">$(x,-y)$</span>;</li>
<li><span class="mathjax-exps">$\forall (x_1, y_1) \in E(F_p), \forall (x_2,y_2) \in E(F_p), x_1\ne x_2$</span>, &#x5219;&#x6709;&#x52A0;&#x6CD5;&#x8FD0;&#x7B97;<span class="mathjax-exps">$(x_1,y_1)+(x_2,y_2)=(x_3,y_3)$</span>. &#x5176;&#x4E2D;, <span class="mathjax-exps">$x_3\equiv \lambda^2-x_1-x_2\mod p, y_3\equiv \lambda(x_1-x_3)-y_1 \mod p, \lambda\equiv \frac{y_2-y_1}{x_2-x_1} \mod p$</span>;</li>
<li><span class="mathjax-exps">$\forall (x_1,y_1)\in E(F_p), y_1\ne 0$</span>, &#x6709;&#x52A0;&#x6CD5;&#x8FD0;&#x7B97;<span class="mathjax-exps">$2(x_1,y_1) = (x_1,y_1)+(x_1,y_1)=(x_3,y_3)$</span>. &#x5176;&#x4E2D;, <span class="mathjax-exps">$x_3\equiv\lambda^2 - 2x_1 \mod p, y_3 \equiv\lambda(x_1-x_3)-y_1\mod p, \lambda\equiv\frac{3x_1^2+a}{2y_1}\mod p$</span>;</li>
</ul>
<p>Hasse&#x5B9A;&#x7406;: &#x4EA4;&#x6362;&#x7FA4;<span class="mathjax-exps">$E(F_p)$</span>&#x4E2D;&#x7684;&#x70B9;&#x7684;&#x4E2A;&#x6570;&#x6EE1;&#x8DB3;<span class="mathjax-exps">$p+1-2\sqrt{p}\le \#(E(F_p)) \le p+1+2\sqrt{p}$</span>;<br>
Hasse&#x5B9A;&#x7406;: &#x4EA4;&#x6362;&#x7FA4;<span class="mathjax-exps">$E(F_p)$</span>&#x4E2D;&#x7684;&#x70B9;&#x7684;&#x4E2A;&#x6570;&#x6EE1;&#x8DB3;<span class="mathjax-exps">$p+1-2\sqrt{p}\le |E(F_p)| \le p+1+2\sqrt{p}$</span>;</p>
<p>&#x82E5;<span class="mathjax-exps">$|E(F_p)| = p + 1$</span>, &#x90A3;&#x4E48;<span class="mathjax-exps">$E(F_p)$</span>&#x79F0;&#x4E3A;&#x662F;&#x8D85;&#x5947;&#x5F02;&#x7684;, &#x5426;&#x5219;&#x79F0;&#x4E3A;&#x975E;&#x8D85;&#x5947;&#x5F02;&#x7684;. ANS X9.62&#x4E2D;&#x89C4;&#x5B9A;&#x7684;&#x692D;&#x5706;&#x66F2;&#x7EBF;&#x662F;&#x975E;&#x8D85;&#x5947;&#x5F02;&#x7684;;</p>
<p>&#x6CE8;: &#x7EA6;&#x675F;&#x6761;&#x4EF6;<span class="mathjax-exps">$4a^3+27b^2\not\equiv \mod p$</span>&#x662F;&#x7FA4;<span class="mathjax-exps">$F_p$</span>&#x4E0A;&#x692D;&#x5706;&#x516C;&#x5F0F;&#x5149;&#x6ED1;&#x7684;&#x5224;&#x522B;&#x5F0F;, &#x89C1;&#x6C42;&#x89E3;&#x4E00;&#x5143;&#x4E09;&#x6B21;&#x65B9;&#x7A0B;&#x7684;&#x6C42;&#x89E3;: <a href="https://zhuanlan.zhihu.com/p/31151158">&#x5361;&#x5C14;&#x4E39;&#x516C;&#x5F0F;</a>;</p>
<h3 class="mume-header" id="%E5%AE%9A%E4%B9%89%E5%9C%A8%E5%9F%9Ff_2m%E4%B8%8A%E7%9A%84%E6%A4%AD%E5%9C%86%E6%9B%B2%E7%BA%BFtoc"><a href="#toc">&#x5B9A;&#x4E49;&#x5728;&#x57DF;<span class="mathjax-exps">$F_{2^m}$</span>&#x4E0A;&#x7684;&#x692D;&#x5706;&#x66F2;&#x7EBF;</a></h3>

<p></p><div class="mathjax-exps">$$y^2 + xy = x^3 + ax^2 + b\ in\ F_{2^m}, \{b\ne 0, a,b \in F_{2^m}\}$$</div><p></p>
<p>&#x7531;&#x5982;&#x4E0A;&#x7B49;&#x5F0F;&#x89E3;&#x7684;&#x96C6;&#x5408;<span class="mathjax-exps">$(x,y),x,y\in F_{2^m}$</span>&#x53CA;<span class="mathjax-exps">$\mathcal{O}$</span>&#x6240;&#x7EC4;&#x6210;&#x7684;&#x96C6;&#x5408;<span class="mathjax-exps">$E(F_{2^m})$</span>&#x5728;&#x5982;&#x4E0B;&#x4E8C;&#x5143;&#x8FD0;&#x7B97;&#x5B9A;&#x4E49;&#x4E0B;&#x6EE1;&#x8DB3;&#x662F;&#x4E00;&#x4E2A;&#x6709;&#x9650;&#x4EA4;&#x6362;&#x7FA4;:</p>
<ul>
<li><span class="mathjax-exps">$\mathcal{O} + \mathcal{O} = \mathcal{O}$</span>, <span class="mathjax-exps">$\mathcal{O}$</span>&#x5373;&#x4E3A;&#x8BE5;&#x7FA4;&#x7684;&#x5355;&#x4F4D;&#x5143;;</li>
<li><span class="mathjax-exps">$(x,y)+\mathcal{O}=\mathcal{O}+(x,y), \forall (x,y) \in E(F_{2^m})$</span>;</li>
<li><span class="mathjax-exps">$(x,y)+(x,x+y)=\mathcal{O}, \forall (x,y) \in E(F_{2^m})$</span>, &#x7FA4;&#x4E2D;&#x5143;&#x7D20;<span class="mathjax-exps">$(x,y)$</span>&#x7684;&#x9006;<span class="mathjax-exps">$-(x,y)$</span>&#x5373;&#x4E3A;<span class="mathjax-exps">$(x,-y)$</span>;</li>
<li><span class="mathjax-exps">$\forall (x_1, y_1) \in E(F_{2^m}), \forall (x_2,y_2) \in E(F_{2^m}), x_1\ne x_2$</span>, &#x5219;&#x6709;&#x52A0;&#x6CD5;&#x8FD0;&#x7B97;<span class="mathjax-exps">$(x_1,y_1)+(x_2,y_2)=(x_3,y_3)$</span>. &#x5176;&#x4E2D;, <span class="mathjax-exps">$x_3= \lambda^2+\lambda+x_1+x_2+a\ \in\ F_{2^m}, y_3= \lambda(x_1+x_3)+x_3+y_1\ \in\ F_{2^m}, \lambda=\frac{y_2+y_1}{x_2+x_1}\ \in\ F_{2^m}$</span>;</li>
<li><span class="mathjax-exps">$\forall (x_1,y_1)\in E(F_p), x_1\ne 0$</span>, &#x6709;&#x52A0;&#x6CD5;&#x8FD0;&#x7B97;<span class="mathjax-exps">$2(x_1,y_1) = (x_1,y_1)+(x_1,y_1)=(x_3,y_3)$</span>. &#x5176;&#x4E2D;, <span class="mathjax-exps">$x_3=\lambda^2 + \lambda + a\ \in \ F_{2^m}, y_3 = (\lambda+1)x_3 + x_1^{2}\ \in\ F_{2^m}, \lambda=x_1+\frac{y_1}{x_1}\ \in\ F_{2^m}$</span>;</li>
</ul>
<p>Hasse&#x5B9A;&#x7406;: &#x4EA4;&#x6362;&#x7FA4;<span class="mathjax-exps">$E(F_p)$</span>&#x4E2D;&#x7684;&#x70B9;&#x7684;&#x4E2A;&#x6570;&#x6EE1;&#x8DB3;<span class="mathjax-exps">$2^m+1-2\sqrt{2^m}\le \#(E(F_{2^m})) \le 2^m+1+2\sqrt{2^m}$</span>;</p>
<h2 class="mume-header" id="%E6%9C%89%E9%99%90%E5%9F%9F%E5%92%8C%E6%A8%A1%E8%BF%90%E7%AE%97toc"><a href="#toc">&#x6709;&#x9650;&#x57DF;&#x548C;&#x6A21;&#x8FD0;&#x7B97;</a></h2>

<h3 class="mume-header" id="%E6%9C%89%E9%99%90%E5%9F%9F%E4%B8%8A%E7%9A%84%E5%B9%82%E8%BF%90%E7%AE%97toc"><a href="#toc">&#x6709;&#x9650;&#x57DF;&#x4E0A;&#x7684;&#x5E42;&#x8FD0;&#x7B97;</a></h3>

<p>&#x8BB0;<span class="mathjax-exps">$b \in F_q, a \in N^+$</span>, &#x6C42;<span class="mathjax-exps">$x=b^a$</span>:</p>
<ul>
<li><span class="mathjax-exps">$t = a \mod (q - 1)$</span>;</li>
<li><span class="mathjax-exps">$t = 0$</span>:
<ul>
<li><span class="mathjax-exps">$x = 1$</span>;</li>
</ul>
</li>
<li><span class="mathjax-exps">$t \ne 0$</span>:
<ul>
<li><span class="mathjax-exps">$t = t_r || t_{r-1} || \dots || t_1 || t_0, t_r = 1$</span>;</li>
<li><span class="mathjax-exps">$x = b$</span>;</li>
<li><code>for i in (r-1)..=0</code>:
<ul>
<li><span class="mathjax-exps">$x = x^2$</span>;</li>
<li><span class="mathjax-exps">$t_i = 1$</span>:
<ul>
<li><span class="mathjax-exps">$x = b\cdot x$</span></li>
</ul>
</li>
</ul>
</li>
</ul>
</li>
</ul>
<h3 class="mume-header" id="%E6%9C%89%E9%99%90%E5%9F%9F%E4%B8%8A%E7%9A%84%E9%80%86%E8%BF%90%E7%AE%97toc"><a href="#toc">&#x6709;&#x9650;&#x57DF;&#x4E0A;&#x7684;&#x9006;&#x8FD0;&#x7B97;</a></h3>

<p>&#x8BB0;<span class="mathjax-exps">$b \in F_q, b \ne e$</span>, &#x6C42;<span class="mathjax-exps">$b\cdot c = g, c \in F_q$</span>, &#x8FD9;&#x91CC;<span class="mathjax-exps">$c$</span>&#x5C31;&#x79F0;&#x4E3A;<span class="mathjax-exps">$b$</span>&#x7684;&#x9006;<span class="mathjax-exps">$b^{-1}=c$</span>:</p>
<ul>
<li><span class="mathjax-exps">$c = b^{q-2}$</span></li>
</ul>
<h3 class="mume-header" id="lucas%E5%BA%8F%E5%88%97%E7%9A%84%E7%94%9F%E6%88%90toc"><a href="#toc">Lucas&#x5E8F;&#x5217;&#x7684;&#x751F;&#x6210;</a></h3>

<p>&#x8BB0;<span class="mathjax-exps">$P, Q$</span>&#x662F;&#x975E;&#x96F6;&#x6574;&#x6570;, <span class="mathjax-exps">$P, Q$</span>&#x7684;Lucas&#x5E8F;&#x5217;&#x5B9A;&#x4E49;&#x4E3A;:</p>
<ul>
<li><span class="mathjax-exps">$U_0 = 0, U_1 = 1, U_k = P\cdot U_{k-1} - Q\cdot U_{k-2}, k \ge 2$</span>;</li>
<li><span class="mathjax-exps">$V_0 = 2, V_1 = P, V_k = P\cdot V_{k-1} - Q\cdot V_{k-2}, k\ge 2$</span>;</li>
</ul>
<p>&#x82E5;&#x6709;&#x9650;&#x57DF;&#x4E3A;<span class="mathjax-exps">$F_p$</span>, &#x5219;&#x7ED9;&#x5B9A;<span class="mathjax-exps">$k$</span>, &#x6C42;<span class="mathjax-exps">$U_k, V_k$</span>&#x7684;&#x5FEB;&#x901F;&#x7B97;&#x6CD5;:</p>
<ul>
<li><span class="mathjax-exps">$\Delta = P^2 - 4\cdot Q$</span>;</li>
<li><span class="mathjax-exps">$k = k_r || k_{r-1}||\dots || k_1 ||k_0, k_r = 1$</span>;</li>
<li><span class="mathjax-exps">$U = 1, V = P$</span>;</li>
<li><code>for i in (r-1)..0</code>:
<ul>
<li><span class="mathjax-exps">$(U, V) = (U\cdot V\mod p, (V^2 + \Delta\cdot U^2)/2 \mod p)$</span>;</li>
<li>if <span class="mathjax-exps">$k_i = 1$</span>:
<ul>
<li><span class="mathjax-exps">$(U, V) = ((P\cdot U + V)/2 \mod p, (P\cdot U + \Delta\cdot U)/2 \mod p)$</span>;</li>
</ul>
</li>
</ul>
</li>
<li>&#x8F93;&#x51FA;<span class="mathjax-exps">$(U, V)$</span>;</li>
</ul>
<h3 class="mume-header" id="%E7%B4%A0%E6%95%B0%E6%A8%A1%E7%9A%84%E5%B9%B3%E6%96%B9%E6%A0%B9toc"><a href="#toc">&#x7D20;&#x6570;&#x6A21;&#x7684;&#x5E73;&#x65B9;&#x6839;</a></h3>

<p>&#x8BB0;&#x6709;&#x5947;&#x7D20;&#x6570;<span class="mathjax-exps">$p$</span>, &#x6574;&#x6570;<span class="mathjax-exps">$0\le b \lt p$</span>, &#x6C42;&#x5176;&#x6A21;&#x7684;&#x5E73;&#x65B9;&#x6839;<span class="mathjax-exps">$y^2 \equiv b \mod p$</span>;</p>
<p>&#x82E5;<span class="mathjax-exps">$b = 0$</span>, &#x5219;<span class="mathjax-exps">$y= 0$</span>. &#x82E5;<span class="mathjax-exps">$b \ne 0$</span>, &#x5219;<span class="mathjax-exps">$b$</span>&#x6709;0&#x4E2A;&#x6216;2&#x4E2A;&#x6A21;<span class="mathjax-exps">$p$</span>&#x7684;&#x5E73;&#x65B9;&#x6839;(&#x5B58;&#x5728;&#x5E73;&#x65B9;&#x6839;<span class="mathjax-exps">$y$</span>, &#x5219;&#x53E6;&#x4E00;&#x4E2A;&#x5E73;&#x65B9;&#x6839;&#x4E3A;<span class="mathjax-exps">$p-y$</span>).</p>
<ul>
<li><span class="mathjax-exps">$p \equiv 3 \mod 4$</span>:
<ul>
<li><span class="mathjax-exps">$p = 4\cdot u + 3, u \in N^+$</span>;</li>
<li><span class="mathjax-exps">$y = b^{u+1} \mod p$</span>;</li>
<li><span class="mathjax-exps">$z = y^2 \mod p$</span>;</li>
<li><span class="mathjax-exps">$b = z$</span>:
<ul>
<li><span class="mathjax-exps">$y$</span></li>
</ul>
</li>
<li><span class="mathjax-exps">$b \ne z$</span>:
<ul>
<li>&#x4E0D;&#x5B58;&#x5728;&#x6A21;&#x7684;&#x5E73;&#x65B9;&#x6839;;</li>
</ul>
</li>
</ul>
</li>
<li><span class="mathjax-exps">$p \equiv 5 \mod 8, p = 8\cdot u + 5, u \in N^+$</span>:
<ul>
<li><span class="mathjax-exps">$\gamma = (2\cdot b)^u \mod p$</span>;</li>
<li><span class="mathjax-exps">$i = 2\cdot g \cdot \gamma^2\mod p$</span>;</li>
<li><span class="mathjax-exps">$y = b \cdot \gamma \cdot (i-1)\mod p$</span>;</li>
<li><span class="mathjax-exps">$z = y^2 \mod p$</span>;</li>
<li><span class="mathjax-exps">$b = z$</span>:
<ul>
<li><span class="mathjax-exps">$y$</span>;</li>
</ul>
</li>
<li><span class="mathjax-exps">$b \ne z$</span>:
<ul>
<li>&#x4E0D;&#x5B58;&#x5728;&#x6A21;&#x7684;&#x5E73;&#x65B9;&#x6839;;</li>
</ul>
</li>
</ul>
</li>
<li><span class="mathjax-exps">$p \equiv 1 \mod 4, p = 4\cdot u + 1, u \in N^+$</span>:
<ul>
<li><span class="mathjax-exps">$Q = b$</span>;</li>
<li><code>loop</code>:
<ul>
<li>&#x968F;&#x673A;&#x751F;&#x6210;&#x4E00;&#x4E2A;&#x6574;&#x6570;<span class="mathjax-exps">$0\le P &lt; p$</span>;</li>
<li>&#x8BA1;&#x7B97;Lucas&#x5E8F;&#x5217;<span class="mathjax-exps">$U = U_{2\cdot u+1} \mod p, V = V_{2\cdot u + 1} \mod p$</span>;</li>
<li><span class="mathjax-exps">$V^2 \equiv 4\cdot Q \mod p$</span>:
<ul>
<li><span class="mathjax-exps">$y = V/2$</span> and <code>break</code>;</li>
</ul>
</li>
<li><span class="mathjax-exps">$U \not\equiv \pm 1 \mod p$</span>:
<ul>
<li>&#x4E0D;&#x5B58;&#x5728;&#x6A21;&#x7684;&#x5E73;&#x65B9;&#x6839;, <code>break</code>;</li>
</ul>
</li>
</ul>
</li>
</ul>
</li>
</ul>
<h3 class="mume-header" id="%E8%BF%B9%E5%92%8C%E5%8D%8A%E8%BF%B9%E5%87%BD%E6%95%B0toc"><a href="#toc">&#x8FF9;&#x548C;&#x534A;&#x8FF9;&#x51FD;&#x6570;</a></h3>

<p>&#x8BB0;&#x6709;&#x57DF;&#x5143;&#x7D20;<span class="mathjax-exps">$\alpha in F_{2^m}$</span>, &#x5219;&#x8FF9;&#x5B9A;&#x4E49;&#x4E3A;<span class="mathjax-exps">$Tr(\alpha) = \alpha + \alpha^2 + \alpha^{2^2} + \dots + \alpha^{2^{m-1}}$</span>, &#x534A;&#x8FF9;&#x5B9A;&#x4E49;&#x4E3A;<span class="mathjax-exps">$Hf(\alpha) = \alpha^{4^0} + \alpha^{4^1} + \alpha^{4^2} + \dots + \alpha^{4^{(m-1)/2}}$</span>. <span class="mathjax-exps">$F_{2^m}$</span>&#x7684;&#x4E00;&#x534A;&#x5143;&#x7D20;&#x7684;&#x8FF9;&#x662F;0, &#x53E6;&#x4E00;&#x534A;&#x5143;&#x7D20;&#x7684;&#x8FF9;&#x662F;1;</p>
<p>&#x82E5;&#x91C7;&#x7528;&#x591A;&#x9879;&#x5F0F;&#x57FA;&#x7684;&#x5F62;&#x5F0F;&#x8868;&#x793A;<span class="mathjax-exps">$F_{2^m}$</span>&#x7684;&#x5143;&#x7D20;, &#x5219;&#x8FF9;<span class="mathjax-exps">$Tr$</span>&#x548C;&#x534A;&#x8FF9;<span class="mathjax-exps">$Hf$</span>&#x7684;&#x8BA1;&#x7B97;&#x5982;&#x4E0B;:</p>
<ul>
<li><span class="mathjax-exps">$Tr = \alpha, Hf = \alpha$</span>;</li>
<li><code>for i in 1..=(m-1)</code>:
<ul>
<li><span class="mathjax-exps">$Tr = Tr^2 + \alpha$</span>;</li>
</ul>
</li>
<li><code>for i in 1..=(m-1)/2</code>:
<ul>
<li><span class="mathjax-exps">$Hf = Hf^2$</span>;</li>
<li><span class="mathjax-exps">$Hf = Hf^2 + \alpha$</span>;</li>
</ul>
</li>
</ul>
<h3 class="mume-header" id="f_2m%E4%B8%8A%E7%9A%84%E4%BA%8C%E6%AC%A1%E7%AD%89%E5%BC%8F%E6%B1%82%E8%A7%A3toc"><a href="#toc"><span class="mathjax-exps">$F_{2^m}$</span>&#x4E0A;&#x7684;&#x4E8C;&#x6B21;&#x7B49;&#x5F0F;&#x6C42;&#x89E3;</a></h3>

<p>&#x8BB0;&#x6709;<span class="mathjax-exps">$\beta \in F_{2^m}$</span>, &#x6C42;&#x89E3;&#x7B49;&#x5F0F;<span class="mathjax-exps">$z^2 + z = \beta$</span>, &#x7B49;&#x5F0F;&#x7684;&#x89E3;&#x7684;&#x4E2A;&#x6570;&#x4E3A;<span class="mathjax-exps">$2-2\cdot Tr(\beta)$</span>. &#x82E5;<span class="mathjax-exps">$\beta = 0$</span>, &#x5219;<span class="mathjax-exps">$z=0,1$</span>. &#x82E5;<span class="mathjax-exps">$\beta \ne 0$</span>, &#x4E14;&#x5B58;&#x5728;&#x89E3;<span class="mathjax-exps">$z$</span>, &#x5219;&#x53E6;&#x4E00;&#x4E2A;&#x89E3;&#x4E3A;<span class="mathjax-exps">$z+1$</span>;</p>
<ul>
<li>&#x82E5;<span class="mathjax-exps">$F_{2^m}$</span>&#x7684;&#x5143;&#x7D20;&#x4F7F;&#x7528;&#x89C4;&#x8303;&#x57FA;&#x8868;&#x793A;:
<ul>
<li><span class="mathjax-exps">$\beta = \beta_0||\beta_1||\dots || \beta_{m-1}$</span>;</li>
<li><span class="mathjax-exps">$z_0 = 0$</span>;</li>
<li><code>for i in 1..=(m-1)</code>:
<ul>
<li><span class="mathjax-exps">$z_i = z_{i-1}\oplus \beta_i$</span>;</li>
</ul>
</li>
<li><span class="mathjax-exps">$z = z_0 || z_1 ||\dots || z_{m-1}$</span>;</li>
<li><span class="mathjax-exps">$\gamma = z^2 + z$</span>;</li>
<li><span class="mathjax-exps">$\gamma = \beta$</span>:
<ul>
<li><span class="mathjax-exps">$z$</span>;</li>
</ul>
</li>
<li><span class="mathjax-exps">$\gamma \ne \beta$</span>:
<ul>
<li>&#x4E0D;&#x5B58;&#x5728;&#x89E3;;</li>
</ul>
</li>
</ul>
</li>
<li>&#x82E5;<span class="mathjax-exps">$F_{2^m}$</span>&#x7684;&#x5143;&#x7D20;&#x4F7F;&#x7528;&#x591A;&#x9879;&#x5F0F;&#x57FA;&#x8868;&#x793A;:
<ul>
<li><span class="mathjax-exps">$z = Hf(\beta)$</span>;</li>
<li><span class="mathjax-exps">$\gamma = z^2 + z$</span>;</li>
<li><span class="mathjax-exps">$\gamma = \beta$</span>:
<ul>
<li><span class="mathjax-exps">$z$</span>;</li>
</ul>
</li>
<li><span class="mathjax-exps">$\gamma \ne \beta$</span>:
<ul>
<li>&#x4E0D;&#x5B58;&#x5728;&#x89E3;;</li>
</ul>
</li>
</ul>
</li>
</ul>
<h3 class="mume-header" id="%E9%AA%8C%E8%AF%81%E7%94%9F%E6%88%90%E5%AD%90%E7%9A%84%E9%98%B6%E7%9A%84%E5%90%88%E6%B3%95%E6%80%A7toc"><a href="#toc">&#x9A8C;&#x8BC1;&#x751F;&#x6210;&#x5B50;&#x7684;&#x9636;&#x7684;&#x5408;&#x6CD5;&#x6027;</a></h3>

<p>&#x8BB0;&#x6709;&#x7D20;&#x6570;<span class="mathjax-exps">$p$</span>, <span class="mathjax-exps">$1\lt b\lt p, k\in N^+$</span>, &#x9A8C;&#x8BC1;<span class="mathjax-exps">$k$</span>&#x662F;&#x5426;&#x662F;<span class="mathjax-exps">$&lt;b&gt; \mod p$</span>&#x7684;&#x9636;:</p>
<ul>
<li>&#x627E;&#x51FA;<span class="mathjax-exps">$k$</span>&#x7684;&#x7D20;&#x9664;&#x6570;&#x96C6;<span class="mathjax-exps">$D$</span>;</li>
<li><span class="mathjax-exps">$g^k \not\equiv 1\mod p$</span>:
<ul>
<li><code>return false</code>;</li>
</ul>
</li>
<li><code>for i in D</code>:
<ul>
<li><span class="mathjax-exps">$g^{k/l} \equiv 1\mod p$</span>:
<ul>
<li><code>return false</code>;</li>
</ul>
</li>
</ul>
</li>
<li><code>return true</code>;</li>
</ul>
<h3 class="mume-header" id="%E7%94%9F%E6%88%90%E5%AD%90%E9%98%B6%E7%9A%84%E8%AE%A1%E7%AE%97toc"><a href="#toc">&#x751F;&#x6210;&#x5B50;&#x9636;&#x7684;&#x8BA1;&#x7B97;</a></h3>

<p>&#x8BB0;&#x6709;&#x7D20;&#x6570;<span class="mathjax-exps">$p$</span>, <span class="mathjax-exps">$1\lt b\lt p$</span>, &#x6C42;<span class="mathjax-exps">$&lt;b&gt; \mod p$</span>&#x7684;&#x9636;:</p>
<ul>
<li><span class="mathjax-exps">$a = b, j = 1$</span>;</li>
<li><code>loop</code>:
<ul>
<li><span class="mathjax-exps">$a = a\cdot b\mod p, j = j + 1$</span>;</li>
<li><span class="mathjax-exps">$a \le 1$</span>:
<ul>
<li><code>break</code>;</li>
</ul>
</li>
</ul>
</li>
<li>&#x8F93;&#x51FA;<span class="mathjax-exps">$j$</span>;</li>
</ul>
<h3 class="mume-header" id="%E6%B1%82%E6%8C%87%E5%AE%9A%E9%98%B6%E6%95%B0%E7%9A%84%E7%94%9F%E6%88%90%E5%AD%90toc"><a href="#toc">&#x6C42;&#x6307;&#x5B9A;&#x9636;&#x6570;&#x7684;&#x751F;&#x6210;&#x5B50;</a></h3>

<p>&#x8BB0;&#x6709;&#x7D20;&#x6570;<span class="mathjax-exps">$p$</span>, &#x548C;&#x53EF;&#x6574;&#x9664;<span class="mathjax-exps">$p-1$</span>&#x7684;&#x6574;&#x6570;<span class="mathjax-exps">$T$</span>, &#x6C42;&#x9636;&#x6570;&#x4E3A;<span class="mathjax-exps">$T$</span>&#x7684;&#x751F;&#x6210;&#x5B50;<span class="mathjax-exps">$u, u\in F_p$</span>:</p>
<ul>
<li><code>loop</code>:
<ul>
<li>&#x968F;&#x673A;&#x751F;&#x6210;&#x4E00;&#x4E2A;&#x6574;&#x6570;<span class="mathjax-exps">$1 \lt b \lt p$</span>;</li>
<li>&#x8BA1;&#x7B97;<span class="mathjax-exps">$&lt;b&gt;\mod p$</span>&#x7684;&#x9636;<span class="mathjax-exps">$k$</span>;</li>
<li>if <span class="mathjax-exps">$k = n\cdot T, n\in N^+$</span>:
<ul>
<li><code>break</code>;</li>
</ul>
</li>
</ul>
</li>
<li><span class="mathjax-exps">$u = g^{k/T} \mod p$</span>;</li>
</ul>
<h2 class="mume-header" id="%E6%9C%89%E9%99%90%E5%9F%9F%E4%B8%8A%E7%9A%84%E5%A4%9A%E9%A1%B9%E5%BC%8Ftoc"><a href="#toc">&#x6709;&#x9650;&#x57DF;&#x4E0A;&#x7684;&#x591A;&#x9879;&#x5F0F;</a></h2>

<h3 class="mume-header" id="%E6%9C%89%E9%99%90%E5%9F%9F%E4%B8%8A%E7%9A%84%E5%A4%9A%E9%A1%B9%E5%BC%8Fgcd%E6%B1%82%E8%A7%A3toc"><a href="#toc">&#x6709;&#x9650;&#x57DF;&#x4E0A;&#x7684;&#x591A;&#x9879;&#x5F0F;GCD&#x6C42;&#x89E3;</a></h3>

<p>&#x8BB0;&#x6709;&#x591A;&#x9879;&#x5F0F;<span class="mathjax-exps">$f(t), g(t)\ne 0$</span>, &#x5B83;&#x4EEC;&#x7684;&#x7CFB;&#x6570;&#x5728;<span class="mathjax-exps">$F_q$</span>&#x4E2D;, <span class="mathjax-exps">$GCD(f(t), g(t))$</span>&#x6C42;&#x89E3;&#x5982;&#x4E0B;:</p>
<ul>
<li><span class="mathjax-exps">$a(t) = f(t), b(t) = g(t)$</span>;</li>
<li><code>while b(t) != 0</code>:
<ul>
<li><span class="mathjax-exps">$c(t) = remainder(a(t)/b(t))$</span>;</li>
<li><span class="mathjax-exps">$a(t) = b(t)$</span>;</li>
<li><span class="mathjax-exps">$b(t) = c(t)$</span>;</li>
</ul>
</li>
<li>&#x8BB0;<span class="mathjax-exps">$\alpha$</span>&#x4E3A;<span class="mathjax-exps">$a(t)$</span>&#x6700;&#x9AD8;&#x6B21;&#x5E42;&#x7684;&#x7CFB;&#x6570;;</li>
<li>&#x8F93;&#x51FA;<span class="mathjax-exps">$\alpha^{-1}\cdot a(t)$</span>;</li>
</ul>
<h3 class="mume-header" id="%E8%AE%A1%E7%AE%97f_2m%E4%B8%8A%E7%9A%84%E4%B8%8D%E5%8F%AF%E7%BA%A6%E5%A4%9A%E9%A1%B9%E5%BC%8F%E7%9A%84%E6%A0%B9toc"><a href="#toc">&#x8BA1;&#x7B97;<span class="mathjax-exps">$F_{2^m}$</span>&#x4E0A;&#x7684;&#x4E0D;&#x53EF;&#x7EA6;&#x591A;&#x9879;&#x5F0F;&#x7684;&#x6839;</a></h3>

<p>&#x8BB0;<span class="mathjax-exps">$f(t)$</span>&#x662F;&#x5EA6;&#x4E3A;<span class="mathjax-exps">$m$</span>&#x7684;&#x4E0D;&#x53EF;&#x7EA6;&#x591A;&#x9879;&#x5F0F;, &#x5219;&#x5176;&#x5728;<span class="mathjax-exps">$F_{2^m}$</span>&#x4E0A;&#x6709;<span class="mathjax-exps">$m$</span>&#x4E2A;&#x975E;&#x91CD;&#x6839;, &#x53EF;&#x6309;&#x5982;&#x4E0B;&#x65B9;&#x6CD5;&#x968F;&#x673A;&#x8BA1;&#x7B97;&#x51FA;&#x5176;&#x4E00;&#x4E2A;&#x6839;:</p>
<ul>
<li><span class="mathjax-exps">$g(t) = f(t)$</span>;</li>
<li><code>while deg(g(t)) &gt; 1</code>:
<ul>
<li>&#x968F;&#x673A;&#x9009;&#x62E9;&#x4E00;&#x4E2A;&#x5143;&#x7D20;<span class="mathjax-exps">$u\in F_{2^m}$</span>;</li>
<li><span class="mathjax-exps">$c(t) = u\cdot t$</span>;</li>
<li><code>for i in 1..(m-1)</code>:
<ul>
<li>$c(t) = (c(t)^2 + u\cdot t)\mod g(t);</li>
</ul>
</li>
<li><span class="mathjax-exps">$h(t) = gcd(c(t), g(t))$</span>;</li>
<li>if !(<span class="mathjax-exps">$h(t)$</span>&#x662F;&#x5E38;&#x91CF;&#x6216;<span class="mathjax-exps">$deg(g) = deg(h)$</span>):
<ul>
<li>if <span class="mathjax-exps">$2\cdot deg(h)\gt deg(g)$</span>:
<ul>
<li><span class="mathjax-exps">$g(t) = g(t) /h(t)$</span>;</li>
</ul>
</li>
<li>else:
<ul>
<li><span class="mathjax-exps">$g(t) = h(t)$</span>;</li>
</ul>
</li>
</ul>
</li>
</ul>
</li>
<li>&#x8F93;&#x51FA;<span class="mathjax-exps">$g(0)$</span>;</li>
</ul>
<h2 class="mume-header" id="%E6%95%B0%E8%AE%BA%E7%9B%B8%E5%85%B3toc"><a href="#toc">&#x6570;&#x8BBA;&#x76F8;&#x5173;</a></h2>

<p><a href="https://www.cnblogs.com/mengsuenyan/p/12969712.html">&#x6570;&#x8BBA;&#x76F8;&#x5173;</a>;</p>
<h3 class="mume-header" id="jacobi%E7%AC%A6%E5%8F%B7%E7%9A%84%E8%AE%A1%E7%AE%97toc"><a href="#toc">Jacobi&#x7B26;&#x53F7;&#x7684;&#x8BA1;&#x7B97;</a></h3>

<p>&#x8BB0;&#x6709;&#x7D20;&#x6570;<span class="mathjax-exps">$p, p\gt 2$</span>, &#x548C;&#x6574;&#x6570;<span class="mathjax-exps">$a, a\in Z$</span>, &#x5219;Legendre&#x7B26;&#x53F7;<span class="mathjax-exps">$(\frac{a}{p})$</span>&#x5B9A;&#x4E49;&#x4E3A;:</p>
<ul>
<li>&#x82E5;<span class="mathjax-exps">$p$</span>&#x6574;&#x9664;<span class="mathjax-exps">$a$</span>, &#x5219;&#x4E3A;0. &#x5426;&#x5219;:
<ul>
<li>&#x82E5;<span class="mathjax-exps">$\exists x \in Z, a \equiv x^2\mod p$</span>, &#x5219;&#x4E3A;1;</li>
<li>&#x82E5;<span class="mathjax-exps">$\not\exists x \in Z, a \equiv x^2\mod p$</span>, &#x5219;&#x4E3A;-1;</li>
</ul>
</li>
</ul>
<p>Jacobi&#x7B26;&#x53F7;&#x662F;Legendre&#x7B26;&#x53F7;&#x7684;&#x63A8;&#x5E7F;, &#x8BB0;&#x6709;<span class="mathjax-exps">$a, a\in Z$</span>, &#x548C;&#x5947;&#x6570;<span class="mathjax-exps">$n, n\gt 1, n= \prod_{i=1}^t p_i^{e_i}$</span>, <span class="mathjax-exps">$p_i$</span>&#x662F;&#x7D20;&#x6570;, &#x5219;Jacobi&#x7B26;&#x53F7;&#x5B9A;&#x4E49;&#x4E3A;<span class="mathjax-exps">$(\frac{a}{n}) = \prod_{i=1}^t (\frac{a}{p_i})^{e_i}$</span>. &#x5176;&#x4E2D;, <span class="mathjax-exps">$(\frac{a}{p_i})$</span>&#x4E3A;Legendre&#x7B26;&#x53F7;. Jacobi&#x7B26;&#x53F7;&#x7684;&#x8BA1;&#x7B97;&#x5982;;:</p>
<ul>
<li><span class="mathjax-exps">$gcd(a, n)\gt 1$</span>:
<ul>
<li><code>return 0</code>;</li>
</ul>
</li>
<li><span class="mathjax-exps">$x = a, y=n, J = 1$</span>;</li>
<li><code>loop</code>:
<ul>
<li><span class="mathjax-exps">$x = x\mod y$</span>;</li>
<li>if <span class="mathjax-exps">$x \gt y/2$</span>:
<ul>
<li><span class="mathjax-exps">$x = y-x$</span>;</li>
<li>if <span class="mathjax-exps">$y\equiv 3 \mod 4$</span>:
<ul>
<li><span class="mathjax-exps">$J = -J$</span>;</li>
</ul>
</li>
</ul>
</li>
<li><code>while x &gt; 4 &amp;&amp; x % 4 = 0:</code>
<ul>
<li><span class="mathjax-exps">$x = x/4$</span>;</li>
</ul>
</li>
<li>if <span class="mathjax-exps">$x &gt; 2$</span>&#x4E14;<span class="mathjax-exps">$x%2 = 0$</span>:
<ul>
<li><span class="mathjax-exps">$x = x/2$</span>;</li>
<li>if <span class="mathjax-exps">$y \equiv \pm 3\mod 8$</span>:
<ul>
<li><span class="mathjax-exps">$J = -J$</span>;</li>
</ul>
</li>
</ul>
</li>
<li>if <span class="mathjax-exps">$x = 1$</span>:
<ul>
<li><code>break J</code>;</li>
</ul>
</li>
<li>if <span class="mathjax-exps">$x \equiv 3\mod 4$</span>&#x4E14;<span class="mathjax-exps">$y\equiv 3\mod 4$</span>:
<ul>
<li><span class="mathjax-exps">$J = -J$</span>;</li>
</ul>
</li>
<li><span class="mathjax-exps">$swap(x,y)$</span>;</li>
</ul>
</li>
</ul>
<p>&#x6CE8;: &#x82E5;<span class="mathjax-exps">$n=q$</span>, &#x5219;Jacobi&#x7B26;&#x53F7;<span class="mathjax-exps">$(\frac{a}{p})=a^{(p-1)/2}\mod p$</span>;</p>
<h3 class="mume-header" id="%E6%B1%82%E6%AD%A3%E6%95%B4%E6%95%B0%E6%A8%A12%E7%9A%84%E6%AC%A1%E5%B9%82%E7%9A%84%E5%B9%B3%E6%96%B9%E6%A0%B9toc"><a href="#toc">&#x6C42;&#x6B63;&#x6574;&#x6570;&#x6A21;2&#x7684;&#x6B21;&#x5E42;&#x7684;&#x5E73;&#x65B9;&#x6839;</a></h3>

<p>&#x8BB0;&#x6709;&#x6574;&#x6570;<span class="mathjax-exps">$r&gt;2$</span>, &#x548C;&#x6B63;&#x6574;&#x6570;<span class="mathjax-exps">$a, a &lt; 2^r, a\equiv 1\mod 8$</span>, &#x6C42;<span class="mathjax-exps">$b^2 \equiv a \mod 2^r, b \lt 2^{r-2}$</span>:</p>
<ul>
<li><span class="mathjax-exps">$h = 1$</span>;</li>
<li><span class="mathjax-exps">$b = 1$</span>;</li>
<li><code>for j in 2..=(r-2)</code>:
<ul>
<li>if <span class="mathjax-exps">$h_{j+1}\ne a_{j+1}$</span>(<span class="mathjax-exps">$h_{j+1}$</span>&#x8868;&#x793A;<span class="mathjax-exps">$h$</span>&#x7B2C;<span class="mathjax-exps">$j+1$</span>&#x4F4D;):
<ul>
<li><span class="mathjax-exps">$b_j = 1$</span>;</li>
<li>if <span class="mathjax-exps">$j \lt r/2$</span>:
<ul>
<li><span class="mathjax-exps">$h = (h+2^{j+1}b-2^{2j}) \mod 2^r$</span>;</li>
</ul>
</li>
<li>if <span class="mathjax-exps">$j \ge r/2$</span>:
<ul>
<li><span class="mathjax-exps">$h = (h + 2^{j+1}b) \mod 2^r$</span>;</li>
</ul>
</li>
</ul>
</li>
</ul>
</li>
<li>if <span class="mathjax-exps">$b_{r-2} =1$</span>:
<ul>
<li><span class="mathjax-exps">$b = 2^{r-1}-b$</span>;</li>
</ul>
</li>
</ul>
<h3 class="mume-header" id="%E5%A4%9A%E9%A1%B9%E5%BC%8F%E7%9A%84%E5%B9%82%E6%A8%A1toc"><a href="#toc">&#x591A;&#x9879;&#x5F0F;&#x7684;&#x5E42;&#x6A21;</a></h3>

<p>&#x8BB0;&#x6709;&#x6B63;&#x6574;&#x6570;<span class="mathjax-exps">$k, k\in N^{+}$</span>, &#x591A;&#x9879;&#x5F0F;<span class="mathjax-exps">$f(t), m(t)$</span>, &#x591A;&#x9879;&#x5F0F;&#x7684;&#x7CFB;&#x6570;&#x5728;&#x57DF;<span class="mathjax-exps">$F_q$</span>&#x4E2D;, &#x5219;<span class="mathjax-exps">$f(t)^k \mod m(t)$</span>&#x53EF;&#x8BA1;&#x7B97;&#x5982;&#x4E0B;:</p>
<ul>
<li><span class="mathjax-exps">$k = k_r || k_{r-1} || \dots || k_1 || k_0, k_r = 1$</span>;</li>
<li><span class="mathjax-exps">$u(t) = f(t) \mod m(t)$</span>;</li>
<li><code>for i in (r-1)..=0</code>:
<ul>
<li><span class="mathjax-exps">$u(t)=u(t)^2 \mod m(t)$</span>;</li>
<li><span class="mathjax-exps">$k_i = 1$</span>:
<ul>
<li><span class="mathjax-exps">$u(t) = u(t)\cdot f(t) \mod m(t)$</span>;</li>
</ul>
</li>
</ul>
</li>
<li>&#x8F93;&#x51FA;<span class="mathjax-exps">$u(t)$</span>;</li>
</ul>
<h2 class="mume-header" id="%E5%8F%82%E8%80%83%E8%B5%84%E6%96%99toc"><a href="#toc">&#x53C2;&#x8003;&#x8D44;&#x6599;</a></h2>

<ol>
<li>Standars for Efficient Cryptography 1 (SEC1: Elliptic Curve Cryptography), Daniel R.L.Brown;</li>
<li>&#x7B97;&#x6CD5;&#x5BFC;&#x8BBA;(3th), Thomas H.Cormen;</li>
<li>ANS x9.62;</li>
</ol>

      </div>
      
      
    
    
    
    
    
    
    
    
  
    </body></html>